using System.Collections.Generic;

namespace WenYu.Core.Lexer;

/// <summary>
/// 关键字Trie树（字典树）
/// 用于高效识别关键字，支持紧凑风格（无空格）
/// </summary>
public class KeywordTrie
{
    private readonly TrieNode _root;
    
    public TrieNode Root => _root;
    
    public KeywordTrie()
    {
        _root = new TrieNode();
    }
    
    /// <summary>
    /// 插入关键字到Trie树
    /// </summary>
    public void Insert(string keyword)
    {
        if (string.IsNullOrEmpty(keyword))
            return;
        
        // 确保keyword被正确复制（避免引用问题）
        keyword = keyword.Substring(0);  // 创建字符串副本
            
        var node = _root;
        foreach (char ch in keyword)
        {
            if (!node.Children.ContainsKey(ch))
            {
                node.Children[ch] = new TrieNode();
            }
            node = node.Children[ch];
        }
        node.IsEndOfWord = true;
        node.Word = keyword;  // 存储完整的关键字副本
    }
    
    /// <summary>
    /// 检查是否包含某个关键字
    /// </summary>
    public bool Contains(string word)
    {
        var node = Search(word);
        return node != null && node.IsEndOfWord;
    }
    
    /// <summary>
    /// 搜索字符串对应的节点
    /// </summary>
    private TrieNode? Search(string word)
    {
        var node = _root;
        foreach (char ch in word)
        {
            if (!node.Children.ContainsKey(ch))
            {
                return null;
            }
            node = node.Children[ch];
        }
        return node;
    }
    
    /// <summary>
    /// 检查是否为关键字前缀
    /// </summary>
    public bool StartsWith(string prefix)
    {
        return Search(prefix) != null;
    }
    
    /// <summary>
    /// 从指定位置查找最长匹配的关键字
    /// 返回：(关键字, 长度)，如果没找到返回(null, 0)
    /// </summary>
    public (string? keyword, int length) FindLongestMatch(string source, int startPos)
    {
        var node = _root;
        string? lastKeyword = null;
        int lastLength = 0;
        int currentPos = startPos;
        
        while (currentPos < source.Length)
        {
            char ch = source[currentPos];
            
            // 尝试在Trie树中前进
            if (node.Children.ContainsKey(ch))
            {
                node = node.Children[ch];
                currentPos++;
                
                // 如果当前位置是一个完整关键字，记录它
                if (node.IsEndOfWord)
                {
                    lastKeyword = node.Word;
                    lastLength = currentPos - startPos;
                }
            }
            else
            {
                // 无法继续匹配
                break;
            }
        }
        
        return (lastKeyword, lastLength);
    }
}

/// <summary>
/// Trie树节点
/// </summary>
public class TrieNode
{
    /// <summary>子节点字典</summary>
    public Dictionary<char, TrieNode> Children { get; }
    
    /// <summary>是否为单词结尾</summary>
    public bool IsEndOfWord { get; set; }
    
    /// <summary>完整单词（仅在IsEndOfWord为true时有值）</summary>
    public string? Word { get; set; }
    
    public TrieNode()
    {
        Children = new Dictionary<char, TrieNode>();
        IsEndOfWord = false;
        Word = null;
    }
}

